package com.cloud.basic.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: basic
 * @description: 二叉查找树
 * @author: Cloud
 * @create: 2020/12/1 16:19:19
 */
public class binTree {

    private binTree left;
    private binTree right;
    private binTree root;

    // 数据域
    private Object data;

    private List<binTree> dataList;

    public binTree(binTree left,binTree right,Object data){
        this.left = left;
        this.right = right;
        this.data = data;
    }

    // 将初始的左右孩子值为空
    public binTree(Object data){
        this(null,null,data);
    }

    public binTree(){}

    public void create(Object[] objects){
        dataList = new ArrayList<binTree>();

        // 将一个数组的值依次转换为Node节点
        for (Object object : objects) {
            dataList.add(new binTree(object));
        }

        // 第一个数为根节点
        root = dataList.get(0);

        int length = objects.length;

        // 建立二叉树
        for (int i = 0; i < length / 2; i++) {
            // 左节点
            dataList.get(i).left = dataList.get(i*2+1);
            // 右节点
            if (i*2+2<dataList.size()) {
                dataList.get(i).right = dataList.get(i*2+2);
            }
        }
    }

    // 先序遍历 从根->左->右
    public void preOrder(binTree root){
        if (root != null) {
            System.out.println(root.data);
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    // 中序遍历
    public void middleOrder(binTree root){
        if (root != null) {
            middleOrder(root.left);
            System.out.println(root.data);
            middleOrder(root.right);
        }
    }

    // 后续遍历
    public void afterOrder(binTree root){
        if (root != null) {
            afterOrder(root.left);
            afterOrder(root.right);
            System.out.println(root.data);
        }
    }

    public static void main(String[] args) {
        binTree binTree = new binTree();
        Object []a={2,4,5,7,1,6,12,32,51,22};
        binTree.create(a);
        System.out.println("----------先序遍历--------");
        binTree.preOrder(binTree.root);
        System.out.println("----------中序遍历--------");
        binTree.middleOrder(binTree.root);
        System.out.println("----------后序遍历--------");
        binTree.afterOrder(binTree.root);
    }
}
